from LinkedBinaryTree import LinkedBinaryTree


def build_expression(tokens):
    """构造一颗算数式树"""
    S = []
    for t in tokens:
        if t in '+-*/x':
            S.append(t)
        elif t not in '()':
            S.append(ExpressionTree(t))
        elif t is ')':
            right = S.pop()
            op = S.pop()
            left = S.pop()
            S.append(ExpressionTree(op, left, right))
    return S.pop()


class ExpressionTree(LinkedBinaryTree):
    """算术表达式树"""

    def __init__(self, token, left=None, right=None):
        super().__init__()
        if not isinstance(token, str):
            raise TypeError('token的类型不是字符串')
        self.add_root(token)
        if left is not None:
            if token not in '+-*/':
                raise ValueError('token不是操作符')
            self._attach(self.root(), left, right)

    def __str__(self):
        pieces = []
        self._parenthesize_recur(self.root(), pieces)
        return ''.join(pieces)

    def _parenthesize_recur(self, p, result):
        """将表达式用字符串表示"""
        if self.is_leaf(p):
            result.append(p.element())
        else:
            result.append('(')
            if self.left(p) is not None:
                self._parenthesize_recur(self.left(p), result)
            result.append(p.element())
            if self.right(p) is not None:
                self._parenthesize_recur(self.right(p), result)
            result.append(')')

    def evaluate(self, par={}):
        """计算算术表达式的值
        :param par:是一个字典，里面是可以是参数的数值,如果表达式数值是字母时
        """
        return self._evaluate_recur(self.root(), par)

    def _evaluate_recur(self, p, par):
        """计算节点p的表达式值"""
        if self.is_leaf(p):
            return float(par.get(p.element(),p.element()))
        else:
            op = p.element()
            left_val = self._evaluate_recur(self.left(p), par)
            right_val = self._evaluate_recur(self.right(p), par)
            if op == '+':
                return left_val + right_val
            elif op == '-':
                return left_val - right_val
            elif op == '/':
                return left_val / right_val
            else:
                return left_val * right_val


if __name__ == '__main__':
    E = build_expression('((2+2)*2)')
    print(E)
    print(E.evaluate())
